from typing import *
from heapq import heapify, heappop, heappush
from cmath import inf


class Solution:
    def minimumTime(
        self, n: int, edges: List[List[int]], disappear: List[int]
    ) -> List[int]:
        nexts = [[] for _ in range(n)]
        for u, v, l in edges:
            nexts[u].append((v, l))
            nexts[v].append((u, l))
        q = [(0, 0)]
        heapify(q)
        ans = [-1 for _ in range(n)]
        while q:
            t, p = heappop(q)
            if ans[p] == -1 or t < ans[p]:
                ans[p] = t
                for np, l in nexts[p]:
                    anp = t + l
                    if disappear[np] > anp and ans[np] == -1 or ans[np] > anp:
                        heappush(q, (anp, np))
        return ans


s = Solution()
print(s.minimumTime(3, [[0, 1, 2], [1, 2, 1], [0, 2, 4]], [1, 3, 5]))
# print(s.minimumTime(3, [[0, 1, 2], [1, 2, 1], [0, 2, 4]], [1, 1, 5]))
